package tree.ordertraversal;

import tree.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Classname : BinaryTreeInorderTraversal
 * @Description :
 * <a href="https://leetcode.cn/problems/binary-tree-inorder-traversal/">94. 二叉树的中序遍历</a>
 * @Author : chentianyu
 * @Date 2023/1/23 16:02
 */


public class BinaryTreeInorderTraversal {

    /**
     * 栈循环实现中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.right != null) stack.push(cur.right);
            if (cur.left == null) inorder.add(cur.val);  // 当前节点无左子节点才遍历
            else {
                stack.push(new TreeNode(cur.val));  // 占位节点没有子节点
                stack.push(cur.left);
            }
        }
        return inorder;
    }


    /**
     * 递归实现中序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> inorder = new ArrayList<>();
        inorderTraversalHelper(inorder, root);
        return inorder;
    }

    private void inorderTraversalHelper(List<Integer> inorder, TreeNode root) {
        if (root == null) return ;

        inorderTraversalHelper(inorder, root.left);
        inorder.add(root.val);
        inorderTraversalHelper(inorder, root.right);
    }
}
